//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
/*#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

#include <iostream>
#include <fstream>*/
#include "utils.h"
#include "factory_pattern.h"
#include "strategy.h"
/*
  using namespace boost;
  typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;
  typedef graph_traits < Graph >::edge_descriptor Edge;
  typedef graph_traits < Graph >::vertex_descriptor Vertex;
  typedef std::pair<int, int> E;
  typedef std::pair<double, double> V;
*/
int
main()
{
/*  using namespace boost;
  typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;

//  typedef adjacency_list < vecS, vecS, undirectedS, no_property, property < edge_weight_t, int > > Graph;
  typedef graph_traits < Graph >::edge_descriptor Edge;
  typedef graph_traits < Graph >::vertex_descriptor Vertex;
  typedef std::pair<int, int> E;
  typedef std::pair<double, double> V;
*/
	Graph_Factory *gf = new Complete_Graph();
	Graph *g = gf->createGraph("graph-125.txt");
/*
	Graph_Factory *gf2 = new Delaunay_Triangle();
	Graph *dt = gf2->createGraph("graph-125.txt");*/
	
	//Graph *g2 = gf->Delaunay_Triangle::createDelaunayTriangleGraph("graph-125.txt");


#if 0
  int _numVertex = 0;  
  V *vertex_array;
  E *edge_array;
  double *weights;
  
  
  std::ifstream fin("graph-5.txt");
  fin >> _numVertex;
  std::cout << "numVertex= " << _numVertex << std::endl;
  
  vertex_array = new V[_numVertex];
  double pX, pY;
  int point = 0;
  while(!fin.eof())
  {
  	fin >> pX;
  	fin >> pY;
  	if(!fin.eof())
  	{
  		vertex_array[point++] = V(pX, pY);
//  		std::cout << " point= " << point << " x= " << pX << " y= " << pY << std::endl;
  	}
  } 
  fin.close();
  
  
  int numEdges = (((_numVertex - 1) * _numVertex )/ 2 );
  std::cout << "Number of vertex = " << _numVertex << " number of edges = " << numEdges << std::endl;
  edge_array = new E[numEdges];
	weights = new double[numEdges];

  for(int i = 0, j = 0; j < _numVertex - 1; j++)
	{
		for(int k = 0; k < _numVertex; k++)
		{
			if(j < k)
			{
				edge_array[i] = E(j,k);
				weights[i] = pow(vertex_array[j].first - vertex_array[k].first, 2) + pow(vertex_array[j].second - vertex_array[k].second, 2);
//				std::cout << " i= " << i << " j= " << j << " k= " << k << std::endl;
				i++;
			}			
		}
	}
  
  
  
  
  
  //E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3), E(3, 4), E(4, 0), E(4, 1)  };
  //double weights[] = { 0.1, 0.1, 0.2, 0.7, 0.3, 0.1, 0.1, 0.1 };
  std::size_t num_edges = ((_numVertex - 1) * _numVertex )/ 2; // FIXME - use the formula     sizeof(edge_array) / sizeof(E);
  Graph g(edge_array, edge_array + numEdges , weights, _numVertex);
  property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);
#endif  
  std::vector < Edge > spanning_tree;
  
  Strategy *s = new SpecialK();
	std::cout << "On the chards " << s->calculate_tree(g) << "\n";

	Strategy *d = new HeavyP();
	std::cout << "On the chards " << d->calculate_tree(g) << "\n";


  kruskal_minimum_spanning_tree(*g, std::back_inserter(spanning_tree));
#if 0
  std::cout << "Print the edges in the MST:" << std::endl;
  for (std::vector < Edge >::iterator ei = spanning_tree.begin();
       ei != spanning_tree.end(); ++ei) {
    std::cout << source(*ei, g) << " <--> " << target(*ei, g)
      << " with weight of " << weight[*ei]
      << std::endl;
  }
  }
  else
  {
	  std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
	  prim_minimum_spanning_tree(g, &p[0]);
  }
  
  std::ofstream fout("figs/kruskal-eg.dot");
  fout << "graph A {\n"
    << " rankdir=LR\n"
    << " size=\"3,3\"\n"
    << " ratio=\"filled\"\n"
    << " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
  graph_traits<Graph>::edge_iterator eiter, eiter_end;
  for (boost::tie(eiter, eiter_end) = edges(g); eiter != eiter_end; ++eiter) {
    fout << source(*eiter, g) << " -- " << target(*eiter, g);
    if (std::find(spanning_tree.begin(), spanning_tree.end(), *eiter)
        != spanning_tree.end())
      fout << "[color=\"black\", label=\"" << get(edge_weight, g, *eiter)
           << "\"];\n";
    else
      fout << "[color=\"gray\", label=\"" << get(edge_weight, g, *eiter)
           << "\"];\n";
  }
  fout << "}\n";
#endif  
  return EXIT_SUCCESS;
}
